def sift_down(data, low, high): # 开始 low = 0 high = len(data) - 1
    temp = data[low]
    # i j 都是动态变化的
    i = low 
    j = i * 2 + 1 # 左孩子索引

    while j <= high: # 保证有左孩子
        # 如果右孩子存在并且大于左孩子 改变j的指向
        if j + 1 <= high and data[j+1] > data[j]:
            j = j + 1
        
        # 比堆顶大
        if data[j] > temp:
            data[i] = data[j]
            i = j
            j = i * 2 + 1
        else:
            break
    
    data[i] = temp


def heap_sort(data):
    n = len(data)

    # 索引为i的节点的父节点的索引位置为 (i-1)//2
    # 从最后一个节点的父节点开始(这时i = n - 1) 进行下沉操作 - 生成最大堆
    for i in range((n-2)//2, -1, -1):
        sift_down(data, i, n-1)
    
    # 排序 - 每次把堆顶元素换到数组的最后一个元素
    # 对堆顶下沉操作维护堆的性质
    for i in range(n-1, -1, -1):
        data[i], data[0] = data[0], data[i]
        sift_down(data, 0, i-1)

import random
data = [random.randint(0, 100) for _ in range(100)]
print(data)
heap_sort(data)
print(data)